package qjc.g_链表;

import java.util.HashMap;
import java.util.Map;

public class g11_随机链表的复制 {
    /**
     * 如果头节点为空，直接返回 null,初始化当前指针，指向头节点,
     * 创建一个哈希表，用于存储原链表节点和新链表节点的映射关系,
     * 第一次遍历：创建新节点并存储映射关系,为每个原链表节点创建一个新节点，
     * 并将它们存储在哈希表中,移动指针到下一个节点,重置当前指针，再次指向头节点,
     * 第二次遍历：设置新节点的 next 和 random 指针,从哈希表中获取当前节点对应的新节点,
     * 设置新节点的 next 指针,设置新节点的 random 指针,移动指针到下一个节点,
     * 返回新链表的头节点
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

